/**
 * Project of Vehicle Routing Problem with Time Windows implements 
 * some of well-known algorithms for solving VRPTW and presents new 
 * one.
 *
 * @author Michal Drobny  
 */
package heuristic;

import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
import logic.algorithm.Algorithm;
import logic.algorithm.AlgorithmResult;
import logic.algorithm.AlgorithmState;
import logic.car.VehicleProvider;
import logic.destination.Destination;
import logic.evaluator.Evaluator;
import logic.restriction.enumeration.IterationType;
import logic.restrictionAdapter.RestrictionAdapter;
import logic.route.Path;
import logic.route.Route;
import logic.route.RouteFromPaths;

/**
 * Represents the Clarke-Wright method for solving VRP problem.
 * 
 * @author Michal Drobny
 * @date 21.10.2014
 */
public class ClarkeWright implements Algorithm {

	@Override
	public AlgorithmResult compute(Route route, Destination start,
			Evaluator evaluator, RestrictionAdapter restrictionAdapter, VehicleProvider vehicleProvider) {

		if (route == null || start == null || evaluator == null
				|| restrictionAdapter == null || vehicleProvider == null)
			return new AlgorithmResult(AlgorithmState.BAD_PARAMETERS, null,
					route);

		if (!route.getDestinations().contains(start))
			return new AlgorithmResult(AlgorithmState.BAD_START_DESTINATION,
					null, route);

		RouteFromPaths resultRoute = getInitialRoute(start,
				route.getDestinations());

		if (!restrictionAdapter.canIterate(IterationType.ROUTE, resultRoute, vehicleProvider, start))
			return new AlgorithmResult(AlgorithmState.NO_SOLUTION, null, route);

		List<EvaluationNumber> evaluationNumbers = getEvaluationNumbers(route.getDestinations(), start, evaluator);
		while (evaluationNumbers.size() > 1) {
			Collections.sort(evaluationNumbers);
			Iterator<EvaluationNumber> iterator = evaluationNumbers.iterator();
			boolean routeUpdated = false;
			while (iterator.hasNext()) {
				EvaluationNumber evaluationNumber = iterator.next();
				Route testRoute = null;
				if ((testRoute = resultRoute.updateRoute(true, evaluationNumber.getStart(), evaluationNumber.getTarget(), start)) != null && 
						restrictionAdapter.canIterate(IterationType.ROUTE, testRoute, vehicleProvider, start)) {
					restrictionAdapter.iterate(IterationType.ROUTE, 
							resultRoute.updateRoute(false, evaluationNumber.getStart(), evaluationNumber.getTarget(), start), vehicleProvider, start);
					updateEvaluationNumbers(evaluationNumbers, evaluationNumber);
					routeUpdated = true;
					break;
				}
			}

			if (!routeUpdated) {
				return new AlgorithmResult(AlgorithmState.MORE_CYCLE_SOLUTION,
						resultRoute.getCycles(start), route);
			}
		}

		return new AlgorithmResult(AlgorithmState.ONE_CYCLE_SOLUTION,
				resultRoute.getCycles(start), route);
	}

	/**
	 * Updates the set of evaluation numbers depending on the evaluation number,
	 * which was chosen (updateEvaluationNumber). It means, that this method
	 * removes all evaluation numbers, whose are dependent on the start or
	 * target destination of the given updateEvaluationNumber. Those evaluation
	 * numbers are no more usable for Clarke-Wright algorithm.
	 * 
	 * @param evaluationNumbers
	 *            A set of evaluation numbers
	 * @param updateEvaluationNumber
	 *            The chosen evalution number
	 */
	private void updateEvaluationNumbers(
			List<EvaluationNumber> evaluationNumbers,
			EvaluationNumber updateEvaluationNumber) {
		Iterator<EvaluationNumber> iterator = evaluationNumbers.iterator();
		while (iterator.hasNext()) {
			EvaluationNumber number = iterator.next();
			
			if ((number.getStart().equals(updateEvaluationNumber.getTarget()) &&
					number.getTarget().equals(updateEvaluationNumber.getStart())) ||
				(number.getStart().equals(updateEvaluationNumber.getStart()) || 
					number.getTarget().equals(updateEvaluationNumber.getTarget())))
				iterator.remove();
		}
	}

	/**
	 * Gets the set of all evaluation numbers for given destinations, start
	 * destination and evaluator.
	 * 
	 * @param destinations
	 *            The destinations
	 * @param start
	 *            The start destinations
	 * @param evaluator
	 *            The evaluator
	 * @return the set of all evaluation numbers for given destinations, start
	 *         destination and evaluator
	 */
	private List<EvaluationNumber> getEvaluationNumbers(
			List<Destination> destinations, Destination start,
			Evaluator evaluator) {

		List<EvaluationNumber> result = new Vector<EvaluationNumber>();
		for (Destination destToStart : destinations) {

			if (destToStart.equals(start))
				continue;

			for (Destination startToDest : destinations) {
				if (startToDest.equals(destToStart)
						|| (startToDest.equals(start)))
					continue;

				if (evaluator.evaluate(destToStart, startToDest) == -1)
					result.add(new EvaluationNumber(destToStart, startToDest,
							Double.MAX_VALUE));
				else
					result.add(new EvaluationNumber(destToStart, startToDest,
							evaluator.evaluate(destToStart, start)
									+ evaluator.evaluate(start, startToDest)
									- evaluator.evaluate(destToStart,
											startToDest)));
			}
		}

		return result;
	}

	/**
	 * Gets the initial solution route for given destinations and start
	 * destination. The initial solution contains so many cycles as the count of
	 * destinations exclude start destination. It means that for every
	 * destination exclude start destination is created 2 path - one from start
	 * to this destination and second for reverse direction (from this
	 * destination to start).
	 * 
	 * @param start
	 *            The start destination
	 * @param destinations
	 *            The destinations
	 * @return the initial solution for given destinations and start destination
	 */
	private RouteFromPaths getInitialRoute(Destination start,
			List<Destination> destinations) {
		if (!destinations.contains(start))
			return null;

		RouteFromPaths result = new RouteFromPaths();
		for (Destination destination : destinations) {
			if (destination.equals(start))
				continue;

			result.addPath(new Path(start, destination));
			result.addPath(new Path(destination, start));
		}

		return result;
	}

	/**
	 * Inner class which represents the Evaluation Number - that is helper
	 * object for Clarke-Wright method.
	 * 
	 * @author Michal Drobny
	 *
	 */
	private class EvaluationNumber extends Path implements Comparable<EvaluationNumber> {

		private final Double evaluation;

		/**
		 * Constructor.
		 * 
		 * @param start
		 *            The start
		 * @param target
		 *            The target
		 * @param evaluation
		 *            The evaluation
		 */
		public EvaluationNumber(Destination start, Destination target,
				Double evaluation) {
			super(start, target);
			this.evaluation = evaluation;
		}

		/**
		 * Getter for evaluation number.
		 * 
		 * @return The evaluation number
		 */
		public Double getEvaluation() {
			return evaluation;
		}

		@Override
		public int compareTo(EvaluationNumber o) {
			return evaluation.compareTo(o.getEvaluation());
		}
	}
}